package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/26
 * @description: 486. 预测赢家
 * https://leetcode-cn.com/problems/predict-the-winner/
 * 这道题一开始很难理解，但是按照四个数字暴力模拟下来，发现跟 泰波那契数 类似
 * {@link com.leetcode.算法策略相关.递归.A_1137_第N个泰波那契数}
 * 这道题,居然对奇偶性还有奇思妙想.
 */
public class B_486_预测赢家 {


	/**
	 * https://leetcode-cn.com/problems/predict-the-winner/solution/yu-ce-ying-jia-by-leetcode-solution/
	 * 暴力模拟可以参考 [1,5,8,4] 的分解图。
	 * 可以发现：
	 * 在长度为4 的数组中，出现了 [1,2] 的重复计算;
	 * 每一个子数组计算的目标是:
	 * 当前玩家面临此情况时,后面的一系列行动,所能达到的最大收益差!
	 *
	 * @param nums
	 * @return
	 */
	public boolean PredictTheWinner(int[] nums) {
		int len = nums.length;
		//边界判断
		if (len <= 2) {
			return true;
		}
		//dp 的行表示:right 的索引;列表示:left 的索引
		//那么最后的答案就是:dp[0][len-1]
		int[][] dp = new int[len][len];
		//init : dp[i][i] = nums[i] 解释:当前玩家拿走最后一个数的收益.
		for (int i = 0; i < len; i++) {
			dp[i][i] = nums[i];
		}
		//init2: dp[i-1][i] = Math.abs(nums[i-1],nums[i]);解释:当前玩家选择两个数中较大的值,另一个玩家只能选择较小的值,于是 max - min 即当前结果.
		//这个结果是可以贪心的
		for (int i = 1; i < len; i++) {
			dp[i - 1][i] = Math.abs(nums[i] - nums[i - 1]);
		}
		//开始动态规划:dp[left][right]=Math.max(
		//nums[left]-dp[i+1][j],
		//nums[right]-dp[i][j-1]
		//)
		int endIndex = len - 1;
		int dleft = 0, dright = 2;
		int left = 0, right = 2;
		while (true) {
			dp[left][right] = Math.max(nums[left] - dp[left + 1][right], nums[right] - dp[left][right - 1]);
			if (right == endIndex) {
				if (left == 0) {
					break;
				} else {
					dright++;
					right = dright;
					left = 0;
				}
			} else {
				left++;
				right++;
			}
		}
		return dp[0][endIndex] >= 0;

	}

	/**
	 * 证明数组长度为偶数必胜:
	 * 可以将 nums 分为 奇数阵营(第奇数个) 和 偶数阵营(第偶数个)
	 * 那么比较大小的结果一共有三种:1.相等;2.奇数大;3.偶数大
	 * 如果是先手,是可以保证必定拿到所有的数字都是 奇数/偶数 .
	 * 在了解 奇数和大/偶数和大 的前提下,先手必胜.
	 * --
	 * 真牛逼!
	 * @param nums
	 * @return
	 */
	public boolean PredictTheWinnerFasterByOdd(int[] nums){
		int len = nums.length;
		if ((len & 1)==0){
			return true;
		}
		return false;
	}
}
